IL[WKHUHVXOWDQGJRRQ

• *UHHG\

– UHHG\7UHHPHWKRG7

– UHHG\&RQQHFWHG&RPSRQHQWPHWKRG&&

Sequential Segment Heuristic (SSH)

S C

G H

F E D

(5, 3)

(3, 4) (2, 1) (4, 2)

(7, 6) (4, 2)

(3, 1) (8, 1)

(5, 1)

(4, 1) (7, 1) (8, 1) (6, 5)

(8, 2)

(2, 1) (1, 3)

(3, 7) (4, 5)

3DUWLWLRQWKHSODQQLQJKRUL]RQLQWRVPDOOHUVHJPHQW 6ROYHVPDOOHUSUREOHPVE\

IL[WKHUHVXOWDQGJRRQ

Greedy Algorithms

Select arc by its weight (e.g., D

_ij

/P

_ij

in decreasing order)

S C

G H

F E D

B (5, 0)

(3, 0) (2, 0) (4, 0)

(7, 6) (4, 2) (3, 1) (8, 0)

(5, 0)

(4, 0) (7, 0) (8, 0) (6, 5)

(8, 2) (1, 3) (3, 7) (4, 5)

S C

G H

F E D

B (5, 0)

(3, 0) (2, 0)

(7, 6) (4, 2) (3, 1) (8, 0)

(5, 0)

(4, 0) (7, 0) (8, 0) (6, 5)

(8, 2) (1, 3) (3, 7) (4, 5)

*UHHG\7UHH*7 *UHHG\&RQQHFWHG&RPSRQHQW*&&

&RPSXWDWLRQDO([SHULPHQWV

• (QYLURQPHQWVHWWLQJV

–3&ZLWK8%8178LQWHO&RUHL*+]

3URFHVVRU*%5$0

–,3E\*XURELVROYHGXSWRKUDWPRVW –$OJRULWKPVE\&&

• 3UREOHPVHWWLQJV

– WHDPV

– 7UHH JUDSKV

– *HQHUDO JUDSKV

,PSURYHPHQWE\9DOLG,QHTXDOLWLHV

• Add 4 valid inequalities

• Performance of different combinations:

( ),

, , 0, ,

e p

at i it

a A A head a i

y IND v i N i S t T

¦

d z }

1 , 0, , 1

at at p

z dz a A t } T

1 , 0, , 1

at at e p

y dy a A A t } T

1 , 0, , 1

it it

v dv i N t } T

(13) (14) (15) (16) (13): if a perfect arc a connects to an accessible node,

then a is also accessible.

3HUIRUPDQFH&RPSDULVRQV

• Tree graphs

• General graphs

&RQFOXVLRQV

• Restore damaged pipelines ASAP are important to the QoL for refugee

• Pipeline arc restoration problem is a special RCPSP with network structure

• Propose a network compacting scheme

• Propose exact IP models ( , _& , )

• Proposed efficient & effective heuristics

(SSH, GT , GCC)

Advancement of mathematical model of disaster prevention and evacuation planning toward social implementation

November 30-December 1, 2017, Fukuoka, JAPAN

Airspace Evacuation Strategies

Maristany de las Casas, Pedro

The Zuse Institute Berlin: ZIB

Berlin, Germany

Airspace Evacuation Strategies

Ralf Borndörfer, Christoph Grafe, Pedro M. Casas 01.12.2017

Zuse Institute Berlin

Zuse Institute Berlin http://www.zib.de

Description

Interdisciplinary research institute for applied mathematics and high-performance computing.

Cooperations with academia and industry.

Research Units

- Numerical Analysis and Simulation - Visualization and Data Analysis - Optimization

- Scientiﬁc Information Systems - High Performance Computing - Computer Science Research ²

Intro

Problem Motivation

Yellow Ribbon Operation

When Airspaces Need to be Emptied

Intro

Flows Over Time Visualization

Flows Over Time or Dynamic Flows

(1/2)

(2/1)

(2/2) (1/1)

(2/1)

(1/1) A

Labels:(τa,ua)

Intro

Input and Problem Classes

Dynamic Network

A dynamic Network...

N= (D= (V,A), τ,u,S,T) consists of

•a directed graphD= (V,A)

•a transit time function

τ:A→N

•a capacity functionu:A→N

•a set of sourcesS ⊂V

•a set of targetsT ⊂V

(1/1) (2/1) (1/2)

s1 s2

t1 t2

Labels:(τa,ua)

Problem Classes on Dynamic Networks

Given a networkN:= (D:= (V,A), τ,u,S,T)

Problem Extra Input Objective Evacuation

Max Flow Time limit

MaxS − T ﬂow

untilT −

Feasible d-Transshipment

T, Demands d:S ∪ T →Z

d-Flow

untilT? −

Quickest d-Transshipment

Demands d:S ∪ T →Z

Quickest

d-Flow +

Problem Classes Dynamic Max-Flow

Topic Review – Dynamic Maximum Flow

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017

Ford and Fulkerson Dyn. Max Flow Introduction F&F - Dyn. Max Flow strongly poly.

Example: Dynamic Max-Flow Problem

Given a networkN= (D= (V,A), τ,u,S,T)and a time limitT, a dynamicmax-flow problem

seeks to maximize the ﬂow fromStoT inN withinTunit of time.

(1/1) (2/1)

(1/2)

s1 s2

t1 t2

θ Inﬂow(t₁+t₂)

Labels:(τa,ua),T=4,θ=4

Dynamic Max-Flow Formulation

Time Dependent Max-Flow

max

a∈δ⁺(s)

θ∈{0,...,T}

xa(θ)

s.t.

a∈δ⁺(v)

xa(θ) =

a∈δ⁻(v)

xa(θ), ∀v∈V\{s.t}, θ∈[T]

xa(θ)≤ca, ∀a∈A, θ∈[T]

xa(θ)∈N, ∀a∈A, θ∈[T]

Algorithms for Dynamic Max-Flow

Static Max-Flow on Time Expanded Network + Easy to understand and implement

– Size of Time Expanded Network not polynomial

+ Time Expanded Network can be manipulated in applications

→Pseudo-Polynomial algorithm depending onT.

Temporarily Repeated Flow [Ford & Fulkerson 62]

+ No graph transformation depending onTand strongly polynomial.

Time Expanded Network

For a networkN= (D= (V,A), τ,u,S,T)and time limitT Original Network

(1/1) (2/1) (1/2)

s1 s2

t1 t2

Labels:(τa,ua)

Time Expanded NetworkT=2

s2 t2 s1 t1

Problem Classes

Feasible Dynamic Transshipment Problem

Problem Classes on Dynamic Networks

Given a networkN= (D= (V,A), τ,u,S,T)

Problem Extra Input Objective Evacuation

Max Flow Time limit

MaxS − T ﬂow

untilT −

Feasible d-Transshipment

T, Demands d:S ∪ T →Z

d-Flow

untilT? −

Quickest d-Transshipment

Demands d:S ∪ T →Z

Quickest

d-Flow +

Example Dynamic Transshipment Problem

Given a networkN= (D= (V,A), τ,u,S,T), a demand function d:S ∪ T →Z, and an time limitT,

a dynamictransshipment problem

seeks to ﬁnd a ﬂow inNthat satisﬁesdin at mostTtime units.

(1/1) (2/1)

(1/2)

s1 s2

t1 t2

θ Inﬂow(t₁+t₂)

Labels:(τa,ua),d(si) =2,d(ti) =−2,T=3,θ=3

Dyn. Transshipment Feasibility via Dynamic Max-Flow

Graph transformation for an instance I of the Dynamic Transshipment Problem

(1/1) (2/1) (1/2)

(0/2) (0/2)

s1 s2

t1 t2

s t

Labels:(τa,ua),d(si) =2,d(ti) =−2,T=3

Iis feasible iﬀ

maxFlow(s,t,T)≥

s∈S

d(s)

Problem Classes

Quickest d -Transshipment Problem

Topic Review – Quickest Transshipment

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017

Ford and Fulkerson Dyn. Max Flow Introduction F&F - Dyn. Max Flow strongly poly.

Hoppe & Tardos Quickest Transsh. strongly poly.

Quickest Transshipment via Dynamic Max-Flow

Graph transformation for an instance I of the Dynamic Transshipment Problem

(1/1) (2/1) (1/2)

(0/2) (0/2)

s1 s2

t1 t2

s t

Labels:(τa,ua),d(si) =2,d(ti) =−2

Binary Search onT

SetU=bigM,L=0,T=bigM/2 and run a binary search untilTis the smallest value s.t.maxFlow(s,t,T)is feasible.

Algorithms For Quickest Transshipment

Binary Search Algorithm

+ Easy to understand and implement

+ Uses time expanded network→customizable modeling - Uses time expanded network→pseudo polynomial running time Submodular Function min. and Lexicographically Maximum Flows [Hoppe, Tardos 94]

+ Strongly polynomial algorithm - Never(?) implemented so far

Evacuation

Earliest Arrival Transshipments

Topic Review – Earliest Arrival Transshipment

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017

Ford and Fulkerson Dyn. Max Flow Introduction F&F - Dyn. Max Flow strongly poly.

Gale SS-ST Earliest Arrivals Existence

Minieka

Pseudo Poly. Algo for Earliest Arrival Fl.

Richardson & Tardos Pseudo Poly. Algo for Earliest Arrival Tr.

Klinz - Dyn MCFN P-hard

Skutella, EAT inO(in+out) Hoppe & Tardos

Quickest Transsh. strongly poly.

Earliest Arrival Transshipment

Given a networkN= (D= (V,A), τ,u,S,T)and demands d:S × T →R

Diﬀerent evacuation scenarios

mintime needed to send all supplies tot (2) maxamount of ﬂow enteringtat everyθ∈[T] (3)

Optimization Problems for Evacuation

•Optimizing objective (2) we get aQuickest Transshipment

•Optimizing objective (3) we get anEarliest Arrival Transshipment

Example: Quickest Transshipment vs. Earliest Arrival

θ Inﬂow(T, θ)

Earliest Arrival,Quickest Transshipment

Existence of Earliest Arrival Flows

Given a networkN= (D= (V,A), τ,u,S,T)and demands d:S × T →R

Do Earliest Arrival Flows always exist?

•If ﬂow hurries towards the correct sink, yes.

•This can only be ensured if|T |=1.

Theorem [Minieka73]

Earliest arrival ﬂows always exist if there is only one sink.

Existence of Earliest Arrival Flows – The MultiSink Case

Example: The graphD₁with unit transit times

(1) (1) (1)

s1 s2

t1 t2

Labels:ua,d(si) =2,d(ti) =−2

Quickest Transshipment

θ 1 2 1+2

Inﬂowt1 1 1 2 Inﬂowt2 1 1 2

InﬂowT 2 2 4

Earliest Arrival?

θ 1 2 1+2

Inﬂowt1 2 0 2 Inﬂowt2 1 0 1

InﬂowT 3 0 3

Existence of Earliest Arrival Flows – The MultiSink Case

(1) (1) (1)

s1 s2

t1 t2

GraphD₁

(2) (1)

(2)

u v w

x GraphD₂,d(u) =4,d(w) = 2,d(v) =−2,d(x) =−4

Theorem [Schmidt, Skutella 2010]

A networkN allows for an Earliest Arrival Transshipment for all choices of capacities and balances iﬀ the graphDdoes not containD₁orD₂as subgraphs.

Existence of Earliest Arrival Flows – The MultiSink Case

In practice, many multiSink applications can be reformulated.

(1) (1) (1)

(d(t2))

(d(t1)) s1

t1 t2

GraphD₁

Theorem [Richardson, Tardos 2002]

A networkN with multiple sources and a single sink allows for an Earliest Arrival Transshipment for all choices of capacities and balances.

Algorithms for Earliest Arrival

Given a networkN= (D= (V,A), τ,u,S,t)and demands d:{S,t} →R

Successive Shortest Path Algorithm

1: Initialize ﬂowx=0 on time exp. network withTbig enough

2: whiles,tconnected in the residual networkR^exp_N do

3: Augmentxalong shortest(s,t)-path inR^exp_N

4: end while

5: Use gen. path decomposition of Step 3 and temporarily repeat to get dynamic ﬂowx_θ.

6: if xθsatisﬁesdthen

7: return Success

8: else

9: return Fail

Flows with Bridge Capacities Problem Description

Flows with Bridge Capacities

Consider a networkN= (D= (V,A), τ,u,S,T)and demands d:S × T →R

with new type of capacities ba:

θ+τa−1 i=θ

xa(i)≤ba, a∈A, θ∈ {0, . . . ,T}

Classical Capacities

θ xa

1 2 3

Arcahas capacityua=3 ²⁹

Flows with Bridge Capacities

Consider a networkN= (D= (V,A), τ,u,S,T)and demands d:S × T →R

with new type of capacities ba:

θ+τa−1 i=θ

xa(i)≤ba, a∈A, θ∈ {0, . . . ,T} Classical Capacities

θ xa

1 2 3

Bridge Capacities

θ xa

1 2 3

Topic Review – Bridge Capacities

1958 1959 1962 1973 1994 2002 2004 2007 2009 2011 2017

Ford and Fulkerson Dyn. Max Flow Introduction

F&F - Dyn. Max Flow strongly poly.

Gale SS-ST Earliest Arrivals Existence

Minieka

Pseudo Poly. Algo for Earliest Arrival Fl.

Richardson & Tardos Pseudo Poly. Algo for Earliest Arrival Tr.

Klinz - Dyn MCFN P-hard

Skutella, EAT inO(in+out) Melkonian Bridge Capacities Intro & weaklyN P-compl.

Skutella - FPTAS for Bridge Cap.

Hamacher Integer Bridge stronglyN P-compl Hoppe & Tardos

Quickest Transsh. strongly poly.

Flows with Bridge Capacities – Model

Integer Bridge Problem

max

a∈δ⁺(s)

θ∈{0,...,T}

xa(θ)

s.t.

a∈δ⁺(v)

xa(θ) =

a∈δ⁻(v)

xa(θ), ∀v∈V\{s.t},∀θ∈ {1, . . . ,T}

θ+τa−1 i=θ

xa(i)≤ua, ∀a∈A,∀θ∈ {1, . . . ,T} xa(θ)∈N, ∀a∈A,∀θ∈ {1, . . . ,T}

LP-Relaxation no longer feasible!

Note that the bridge constraints destroy total unimodularity!

Airspace Evacuation

Problem Formulation

Input – The Airway Network

Input – Sources, Sinks and Arc Capacities

Sources and Sinks

•Sources: The position (nodes) of a given set of aircraft.

•Sinks: Available airports in the Airway Network (graph).

Arc Capacities

Common arcs have capacity 1 to simulate waiting.

Immediate Start and Airport Capacity

Immediate Start

Aircraft can’t wait at a node.

•Single copy of airports/sources needed.

•Only one unit of ﬂow per source!

Airport Capacity and Multiple Sinks?

•No need for multiple sinks: An airportdoes not demandaircraft.

•BUT it can store amaximum number of aircraft

→"bridge capacity" at a node.

Airspace Evacuation A Graph-Based Algorithm

A Graph-Based Algorithm

Graph Preprocessing

•Time Expansion needed

•Time Expansion does little harm (only one copy of each source and no waiting arcs)

•Airport Filters needed (Airport capacities→Bridges)

A Graph-Based Algorithm

Graph Preprocessing

•Time Expansion needed

•Time Expansion does little harm (only one copy of each source and no waiting arcs)

•Airport Filters needed (Airport capacities→Bridges) Run

AdaptedSuccessive Shortest Path Algorithm

Time Expansion for Airspace Evacuation

Consider the following instances: japan_200_20 and europe_200_20

Japan Europe Original number of nodes 13,978 23,103 Original number of arcs 22,521 102,502 Chosen time limitT[min] 596 550 Nodes after time exp. 1,277,716 8,053,503 Arcs after time exp. 5,267,948 57,884,410

Airport Filters

Original graph

t cap=10

Airport Filter in Time Expanded Network

(10)

t1 t2 tT

θ=1

θ=2

θ=T

af t*

Adapted Successive Shortest Path Algorithm

Successive Shortest Path Algorithm

1: Initialize ﬂowx=0 on time exp. network withTbig enough

2: whiles,tconnected in the residual networkR^exp_N do

3: Augmentxalong shortest(s,t)-path inR^exp_N

4: end while

5: Use gen. path decomposition of Step 3 and temporally repeat to get dynamic ﬂowxθ.

6: if xsatisﬁesd then

7: return Success

8: else

9: return Fail

10:end if

Correctness of the Algorithm

Theorem

Consider a networkN= (D= (V,A), τ,u,s,t)with unit capacities. If there is a ﬂow of valuek, then there are at leastkedge-disjoint (s,t)-paths.

→Max-Flow for fast feasibility check.

Correctness of the Algorithm

Theorem

Consider a networkN= (D= (V,A), τ,u,s,t)with unit capacities. Ifx is a0−1ﬂow with valuek, then the arcs withxa=1contain a set of k edge-disjoint paths.

→If the problem is feasible, Successive Shortest Path ﬁnds a ﬂow of valuekthat can be decomposed.

Running Time

Consider the following instances: japan_200_20 and europe_200_20

Japan Europe Quickest Transshipment [s] 60.2 1,100.6 Earliest Arrival Transshipment [s] 1.8 16.2

Evacuation Duration [min] 377 260

Quickest vs. Earliest Arrival

Earliest vs. Quickest Japan

Quickest vs. Earliest Arrival

Earliest vs. Quickest Europe

Airspace Evacuation Future work

Future Work

•Minimum aircraft separation

•Aircraft Evacuation with constraint resources

•Priority Evacuation

Planning Aircraft Routes is Important!

Advancement of mathematical model of disaster prevention and evacuation planning toward social implementation

November 30-December 1, 2017, Fukuoka, JAPAN

Solving Extremely Large Stochastic Mixed-Integer Programs in Parallel on Distributed Memory

Computing Environments

Yuji Shinano

The Zuse Institute Berlin: ZIB

Berlin, Germany

Solving Extremely Large Stochastic Mixed-Integer

ドキュメント内 Vol.78 MI Lecture Notes|九州大学マス・フォア・インダストリ研究所 math 5acd7940c3b8c (ページ 35-59)

• *UHHG\

– *UHHG\7UHHPHWKRG*7

– *UHHG\&RQQHFWHG&RPSRQHQWPHWKRG*&&

Sequential Segment Heuristic (SSH)

Greedy Algorithms

Select arc by its weight (e.g., D

/P

in decreasing order)

&RPSXWDWLRQDO([SHULPHQWV

• (QYLURQPHQWVHWWLQJV

• 3UREOHPVHWWLQJV

– WHDPV

– 7UHH JUDSKV

– *HQHUDO JUDSKV

,PSURYHPHQWE\9DOLG,QHTXDOLWLHV

• Add 4 valid inequalities

• Performance of different combinations:

¦

3HUIRUPDQFH&RPSDULVRQV

• Tree graphs

• General graphs

&RQFOXVLRQV

• Restore damaged pipelines ASAP are important to the QoL for refugee

• Pipeline arc restoration problem is a special RCPSP with network structure

• Propose a network compacting scheme

• Propose exact IP models ( , & , )

• Proposed efficient & effective heuristics

(SSH, GT , GCC)

Advancement of mathematical model of disaster prevention and evacuation planning toward social implementation

Airspace Evacuation Strategies

Maristany de las Casas, Pedro

The Zuse Institute Berlin: ZIB

Berlin, Germany

Airspace Evacuation Strategies

Zuse Institute Berlin http://www.zib.de

Intro

Problem Motivation

Yellow Ribbon Operation

When Airspaces Need to be Emptied

Intro

Flows Over Time Visualization

Flows Over Time or Dynamic Flows

Intro

Input and Problem Classes

Dynamic Network

Problem Classes on Dynamic Networks

Problem Classes Dynamic Max-Flow

Topic Review – Dynamic Maximum Flow

Example: Dynamic Max-Flow Problem

Dynamic Max-Flow Formulation

Algorithms for Dynamic Max-Flow

Time Expanded Network

Problem Classes

Feasible Dynamic Transshipment Problem

Problem Classes on Dynamic Networks

Example Dynamic Transshipment Problem

Dyn. Transshipment Feasibility via Dynamic Max-Flow

Problem Classes

Quickest d -Transshipment Problem

Topic Review – Quickest Transshipment

Quickest Transshipment via Dynamic Max-Flow

Algorithms For Quickest Transshipment

Evacuation

Earliest Arrival Transshipments

Topic Review – Earliest Arrival Transshipment

Earliest Arrival Transshipment

Example: Quickest Transshipment vs. Earliest Arrival

Existence of Earliest Arrival Flows

Existence of Earliest Arrival Flows – The MultiSink Case

Existence of Earliest Arrival Flows – The MultiSink Case

Existence of Earliest Arrival Flows – The MultiSink Case

Algorithms for Earliest Arrival

Flows with Bridge Capacities Problem Description

Flows with Bridge Capacities

Flows with Bridge Capacities

Topic Review – Bridge Capacities

Flows with Bridge Capacities – Model

Airspace Evacuation

Problem Formulation

– UHHG\7UHHPHWKRG7

– UHHG\&RQQHFWHG&RPSRQHQWPHWKRG&&

• Propose exact IP models ( , _& , )